1. Field of the Invention
The invention relates to the field of program flow information. More particularly, the invention relates to a method and apparatus for using embedded program flow information for binary manipulation.
2. Art Background
Tasks involving binary manipulations include binary translation which is the process of converting binary code targeted for one machine to another machine, and binary optimization which is the process of converting a less efficient binary code to a more efficient binary code. Such tasks are difficult due to the need to generate flow information for the executable file upon which the particular binary manipulation is being performed.
Flow information is information describing the flow of program execution sequences. Flow information includes but is not limited to: control flow information, (such as basic block, superblock, tree, and/or hyperblock successors and predecessors), data flow information (such as register liveness or information concerning assignment of variables to registers), data type information, and information about array access patterns, alias information indicating which memory access might be altered as a side effect of some instruction or instruction sequence, identification of idiomatic control structures such as jump tables, and identification of idiomatic data flow information such as stride lengths for array accesses.
Typically, flow information is derived each time the need arises during a binary manipulation. The drawback in having to derive flow information as the need arises is the amount of time consumed in building such information during a binary manipulation.
Problems may be encountered during a binary manipulation if certain necessary flow information is not available. For example, a problem arises during a binary translation if a program being translated has jump tables. To perform an accurate binary translation of a program, the entire flow of the region of interest must be known. A jump instruction in a program being translated may indicate a jump to one of a given number of different locations depending upon a value stored at a register X. If the value of the register X is not known, the binary translation being performed will not produce accurate results.
If a program can be divided into semi-independent sub-units such as modules or procedures, it suffices to know the entire flow of only the sub-unit being manipulated.
The efficiency of a binary-to-binary optimization depends on the level of the detail of the flow information. Thus to turn poor code into good code or good code into better code, more accurate flow information is desirable.
Finally, in program debugging, bug fixing, and tracing activities, certain embedded flow information is desirable to perform such tasks in a more efficient manner. A program being debugged must be traced step by step. For example, in a program being debugged, if a register Y is assigned a value, and the flow information indicates that the value assigned to register Y never gets used in the rest of the program, this detects a potential bug in the program.
With the advent of increased interest in certain tasks involving binary manipulations and given that the generation of flow information is time consuming, there is a need for a method and apparatus to make necessary flow information available during tasks involving binary manipulations.